struct ListNode
{
    int val;
    ListNode * next;
    ListNode() : val(0), next(nullptr)
    {}
    ListNode(int val) : val(val), next(nullptr)
    {}
    ListNode(int val, ListNode * next) : val(val), next(next)
    {}
};


class Solution 
{
public:
    ListNode* reverseList(ListNode* head) 
    {
        if(head == nullptr || head->next == nullptr)
        {
            return head;
        }
        ListNode * _dummyHead = new ListNode(0, head);
        ListNode * left = _dummyHead;
        ListNode * mid = _dummyHead->next;
        ListNode * right = _dummyHead->next->next;

        while (mid != nullptr)
        {
            mid->next = left;
            left = mid;
            mid = right;
            if(mid == nullptr)
            {
                break;
            }
            right = right->next;
        }
        head->next = nullptr;
        delete _dummyHead;
        return left;
    }
};

#include <iostream>
#include <vector>
using namespace std;

// 辅助函数：根据数组创建链表
ListNode* createList(const vector<int>& nums) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int num : nums) {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    return dummy.next;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

// 释放链表内存
void freeList(ListNode* head) {
    while (head) {
        ListNode* tmp = head;
        head = head->next;
        delete tmp;
    }
}

int main() {
    Solution sol;

    vector<vector<int>> testCases = {
        {1, 2, 3, 4, 5},
        {1},
        {},
        {1, 2},
        {5, 4, 3, 2, 1}
    };

    for (size_t i = 0; i < testCases.size(); ++i) {
        cout << "测试用例 " << i + 1 << " 原链表: ";
        ListNode* head = createList(testCases[i]);
        printList(head);

        ListNode* reversed = sol.reverseList(head);
        cout << "反转后链表: ";
        printList(reversed);
        cout << "------------------------" << endl;

        freeList(reversed);
    }

    return 0;
}
